import React from 'react';

export default function index() {
  // --------------三数之和--------------------
  // 1、
  const getSunOfZero = (nums: number[]) => {
    let result: Array<number>[] = [];
    let front = 0;
    let last = nums.length - 1;
    while (front != last) {
      const nums2 = nums.filter((a) => a !== nums[front] && a !== nums[last]);
      if (nums2.indexOf(0 - (nums[front] + nums[last])) != -1) {
        const current = nums2.indexOf(0 - (nums[front] + nums[last]));
        result.push([nums[front], nums[last], nums[current]]);
      }
      if (Math.abs(nums[front]) > Math.abs(nums[last])) {
        front++;
      } else {
        last--;
      }
    }
    let map = new Map();
    for (let arr of result) {
      arr.sort((a, b) => b - a);
      const key = arr[0];
      if (!map.has(key)) {
        map.set(key, arr);
      }
    }
    return Array.from(map.values());
  };
  // 2、双指针
  const getSunOfZero2 = (nums: number[]) => {
    let result: Array<number>[] = [];
    // 1\边界条件
    if (nums.length < 3) return [];
    // 2/排序 双指针的关键
    const sortNums = nums.sort((a, b) => a - b);
    // 3、循环，先确定第一个数
    for (let i = 0; i < sortNums.length - 2; i++) {
      if (i > 0 && sortNums[i - 1] === sortNums[i]) continue; // 过滤掉第一个数重复的选择
      let left = i + 1;
      let right = sortNums.length - 1;
      while (left < right) {
        const sun: number = sortNums[i] + sortNums[left] + sortNums[right];
        if (sun === 0) {
          result.push([sortNums[i], sortNums[left], sortNums[right]]);
          // 过滤第二个数和第三个数重复的情况
          while (left < right && sortNums[right - 1] === sortNums[right])
            right--;
          while (left < right && sortNums[left + 1] === sortNums[left]) left++;
          left += 1;
          right += 1;
        } else if (sun < 0) {
          //需要一个更大的数
          left++;
        } else {
          right--;
        }
      }
    }
    return result;
  };
  const testSumOfThree = (s: number[]) => {
    // 每次确定第一个=数，通过双指针寻找剩下两个数
    let result: number[][] = [];
    const ss = s.sort((a, b) => a - b);
    for (let i = 0; i < ss.length; i++) {
      let left = i + 1;
      let right = ss.length - 1;
      while (left < right) {
        const sum = s[i] + s[left] + s[right];
        if (sum === 0) {
          result.push([s[i], s[left], s[right]]);
          while (s[left++] === s[left]) left++;
          while (s[right--] === s[right]) right--;
          left += 1;
          right -= 1;
        } else if (sum < 0) {
          left += 1;
        } else {
          right -= 1;
        }
      }
    }
    return result;
  };
  console.log(testSumOfThree([-1, 0, 1, 2, -1, -4]));

  // -------------------------接雨水------------------------------
  // 对于数组中的任何一个位置 i，它能接住的雨水量由它左右两边的最高柱子的较小值（即短板）决定
  // min(leftMaxHight,rightMaxHight)-height(i)
  const getRain = (nums: number[]) => {
    // 边界条件
    if (nums.length <= 2) return 0;
    let rightMax = 0;
    let leftMax = 0;
    let right = nums.length - 1;
    let left = 0;
    let sum = 0;
    // 此遍历
    //对于任意一个位置 i，如果 leftMax 小于 rightMax，那么 leftMax 就是 i 左侧的最大值，
    //而 rightMax 是右侧的某个最大值（可能不是 i 右侧的最大值，但至少是一个足够大的值，可以保证 min(leftMax, rightMax) 的正确性）
    while (right >= left) {
      if (leftMax < rightMax) {
        //此时 leftMax比rightMax小，即当i右边有比rightMax小的我们不会取，若有比rightMax大的，则其一定比leftMax大；所以min(leftMaxHight,rightMaxHight)就为leftMax
        leftMax = Math.max(leftMax, nums[left]);
        sum += leftMax - nums[left];
        left++;
      } else {
        rightMax = Math.max(rightMax, nums[right]);
        sum += rightMax - nums[right];
        right--;
      }
    }
    return sum;
  };
  const getRain2 = (nums: number[]) => {
    let leftMax = 0;
    let rightMax = 0;
    let right = nums.length - 1;
    let left = 0;
    let sum = 0;
    while (left <= right) {
      if (leftMax < rightMax) {
        // 虽然此时rightMax不一定正确，但是可以保证leftMax= min(rightMax,leftMax)
        leftMax = Math.max(leftMax, nums[left]);
        sum += leftMax - nums[left];
        left++;
      } else {
        rightMax = Math.max(rightMax, nums[right]);
        sum += rightMax - nums[right];
        right--;
      }
    }
    return sum;
  };
  console.log(getRain2([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));

  // -----------------------无重复字符最长子串------------------------------
  // 窗口 双指针
  const getMaxLengthNorepeate2 = (s: string) => {
    // 边界条件
    if (s.length < 2) return s.length;
    // 初始化指针
    let right = 0; // 窗口右边
    let left = 0; // 窗口左边
    let currentArr = new Set<String>(); // 窗口内字符，窗口记录当前最长无重复字符串
    let max = 0;
    for (right; right < s.length; right++) {
      const currentChar = s[right];
      while (currentArr.has(currentChar)) {
        // 当遇到重复时清空当前窗口
        currentArr.delete(s[left]);
        left++;
      }
      currentArr.add(s[right]); // 当前窗口内无重复 则将当前数字添加到窗口内
      max = Math.max(max, right - left + 1);
    }
    return max;
  };
  console.log(getMaxLengthNorepeate2('abcddffabcg'));
  const findCharArr = (s: string, p: string) => {
    // 1、边界条件
    if (p.length > s.length) return [];
    // 2、初始化
    const result: number[] = [];
    const resultP = new Array(26).fill(0);
    let left = 0;
    let right = p.length;
    // 转为小写
    const p1 = p.toLowerCase();
    const s1 = s.toLowerCase();
    // 得到p字符串对应的26个字母位置数组
    for (let i = 0; i < p1.length; i++) {
      const char = p1[i];
      const position = char?.charCodeAt(0) - 'a'.charCodeAt(0);
      resultP[position]++;
    }
    // 滑动窗口找到p的异位词
    for (right; right <= s1.length; right++) {
      const currentStr = s1.slice(left, right);
      const currentS = new Array(26).fill(0);
      // 当前选中字符串的字母表位置数组
      for (let j = 0; j < p.length; j++) {
        const char = currentStr[j];
        const position = char?.charCodeAt(0) - 'a'.charCodeAt(0);
        currentS[position]++;
      }
      if (JSON.stringify(currentS) === JSON.stringify(resultP)) {
        result.push(left);
      }
      left++;
    }
    return result;
  };
  console.log(findCharArr('abab', 'ab'));

  // -------------------------数组中和为k的连续子数组--------------------
  const getSumOfK = (nums: number[], k: number): number => {
    if (!nums || nums.length === 0) return 0;

    let result = 0;
    const sumMap = new Map<number, number>();
    sumMap.set(0, 1); // 初始条件：和为0出现1次
    let currentSum = 0;

    for (const num of nums) {
      currentSum += num;

      // 检查是否存在 previousSum = currentSum - k
      if (sumMap.has(currentSum - k)) {
        result += sumMap.get(currentSum - k)!;
      }

      // 更新当前和的计数
      sumMap.set(currentSum, (sumMap.get(currentSum) || 0) + 1);
      console.log(sumMap);
    }

    return result;
  };

  const getSumOfK2 = (nums: number[], k: number): number => {
    if (!nums || nums.length === 0) return 0;

    let result = 0;

    for (let left = 0; left < nums.length; left++) {
      let currentSum = 0;
      for (let right = left; right < nums.length; right++) {
        currentSum += nums[right];
        if (currentSum === k) {
          result++;
        }
      }
    }

    return result;
  };

  // -----------------每次滑动窗口中最大数----------------------------
  const getMaxNumberOfk = (nums: number[], k: number) => {
    let left = 0;
    let right = k - 1;
    let result: number[] = [];
    while (right < nums.length) {
      // 得到滑动窗口中最大值
      let currentMax = nums[left];
      for (let i = left; i <= right; i++) {
        currentMax = Math.max(currentMax, nums[i]);
      }
      result.push(currentMax);
      right++;
      left++;
    }
    return result;
  };
  // 方法二：单调队列
  // 使用队列记录当前窗口数的索引，记录降序索引
  var maxSlidingWindow = function (nums: number[], k: number) {
    const q: number[] = []; // 记录当前窗口中数字的索引
    const result = []; // 最大值
    // 初始化前k个数，将最大数放于队列头
    for (let i = 0; i < k; i++) {
      // 每次将队尾最小的数出队即可得到一个nums值为降序的索引的队列
      // 当前数前面比他小的出队，其后面比他小的排在他后面
      while (q.length && nums[i] >= nums[q[q.length - 1]]) {
        q.pop();
      }
      q.push(i);
    }
    result.push(nums[q[0]]);
    // 从第k+1个数开始处理，得到nums降序的索引队列
    for (let i = k; i < nums.length; i++) {
      // 队尾比当前数小的均出栈，实现降序排列
      while (q.length && nums[i] >= nums[q[q.length - 1]]) {
        q.pop();
      }
      q.push(i);
      // 超过窗口大小的数的索引出栈
      while (q[0] <= i - k) {
        q.shift();
      }
      // 当前窗口第一个数压入
      result.push(nums[q[0]]);
    }
    return result;
  };
  console.log(maxSlidingWindow([4, 3, 11], 3));

  // ------------------------查找字符串中包含目标字符串的最长子串-------------------------
  const findTofS = (s: string, t: string) => {
    // 边界条件
    if (s.length < t.length) return '';
    if (t.length === 1) {
      if (s.includes(t)) return t;
    }
    let right = 0;
    let left = 0;
    let minarr = new Array(s.length);
    let current = []; // 记录当前找到的s中的t的字符
    let tt = t.split('');
    let ss = s.split('');
    console.log(tt);
    while (left < s.length && minarr.length > t.length) {
      // 先找到第一个t中元素
      while (left < s.length && !t.includes(ss[left])) {
        left++;
      }
      current.push(ss[left]);
      right = left;
      // right 往前继续找下面的字符
      while (current.length !== tt.length && right < s.length) {
        // 当前字符在t中但是(不在current中或current中该字母数量与t中不一致）
        right++;
        if (
          t.includes(ss[right]) &&
          (current.indexOf(ss[right]) === -1 ||
            tt.filter((x) => x === ss[right])?.length !==
              current.filter((x) => x === ss[right])?.length)
        ) {
          current.push(ss[right]);
        }
      }
      // 得到更短的子串
      if (current.length === tt.length && right - left + 1 <= minarr.length) {
        minarr = ss.slice(left, right + 1);
        console.log(minarr);
      }
      // 此时已经找到了第一个子串,开始找下一个子串
      current = [];
      left++;
    }
    return minarr.join('');
  };
  // console.log(findTofS('ad0bec0debanc', 'abc'));
  console.log(findTofS('bdab', 'ab'));

  // -------------------- 数组中最大和连续子串-------------
  // 动态规划 转移问题,记住计算过的值 f(n) = f(n-1)+f(n-2)
  // 长度1 到当前位置最大子串 f(1) = x
  // 长度2 到当前位置最大子串 f(2) = Math.max(f(1)+x,x)
  // 长度3 到当前位置最大子串 f(3) = Math.max(f(2)+x,x)
  const maxSun = (nums: number[]) => {
    let pre = 0;
    let maxSum = nums[0];
    nums.forEach((x) => {
      pre = Math.max(pre + x, x);
      maxSum = Math.max(pre, maxSum);
    });
    return maxSum;
  };
  console.log(maxSun([2, 1, -2, 1, 4, -5, 4]));

  // -------------------合并区间---------------------
  const sortRange = (intervals: number[][]) => {
    // 边界条件
    if (intervals.length < 2) {
      return intervals;
    }
    // 按照小区间start排序
    intervals.sort((a, b) => a[0] - b[0]);
    console.log(intervals);
    // 判断区间包裹
    const merge = [intervals[0]];
    console.log(merge);

    for (let i = 1; i < intervals.length; i++) {
      const last = merge[merge.length - 1];
      const current = intervals[i];
      if (last[1] >= current[0]) {
        // 此时可以合并，修改当前子区间的end为最大值即可
        last[1] = Math.max(last[1], current[1]);
      } else {
        merge.push(current);
      }
    }

    return merge;
  };
  console.log(
    sortRange([
      [1, 4],
      [0, 4],
    ])
  );
  // ---------------轮转数组-------------
  const rotationArray = (nums: number[], k: number) => {
    // 边界条件
    if (nums.length < 2) {
      return nums;
    }
    let i = 1;
    while (i <= k) {
      const current = nums.pop();
      if (current || current === 0) {
        nums.unshift(current);
      }
      i++;
    }
    return nums;
  };
  // console.log(rotationArray([2147483647, -2147483648, 33, 219, 0], 4));
  console.log(rotationArray([1, 0], 1));
  // ---------------除自身以外数组的乘积-----------------
  const multiplySum = (nums: number[]) => {
    let left: number[] = [];
    let right: number[] = [];
    let answer: number[] = [];
    left[0] = 1;
    right[nums.length - 1] = 1;
    // nums[i]左边所有数的乘积
    for (let i = 1; i < nums.length; i++) {
      left[i] = left[i - 1] * nums[i - 1];
    }
    // nums[i]右边所有数的乘积
    for (let i = nums.length - 2; i >= 0; i--) {
      right[i] = right[i + 1] * nums[i + 1];
    }
    // nums[i]除自身外所有数的乘积
    for (let i = 0; i < nums.length; i++) {
      answer[i] = left[i] * right[i];
    }
    return answer;
  };
  console.log(multiplySum([1, 2, 3, 4, 5]));

  // --------------------缺少的最小正数---------------------
  // 思路：
  // 长度为N的数组，最小正数在[1,n+1]中，1-n均存在则为n+1；
  //创建一个键值为[1,n]的哈希表（哈希表查找元素为O（1）），遍历数组，哈希表中存在的数组元素标记为1；
  //最后取得标记为0的最小元素
  const getPositiveNum = (nums: number[]) => {
    // 创建哈希表,置所有标记为0
    const l = nums.length;
    const hashTable = new Map();
    for (let i = 1; i <= l; i++) {
      hashTable.set(i, 0);
    }
    // 遍历数组，找到1-n的数对应修改哈希表中的标记
    for (let i = 0; i < l; i++) {
      const current = nums[i];
      if (hashTable.has(current)) {
        hashTable.set(current, 1);
      }
    }
    //查找第一个值为0的元素
    for (const [key, value] of hashTable) {
      if (value === 0) return key;
    }
    return l + 1;
  };
  console.log(getPositiveNum([1, 2, 4, 5]));
  return <div>双指针:1、有序数组考虑对撞指针（数组两端）</div>;
}
